This invention relates generally to complex node representations in PNNI network systems. Particular embodiments of the invention provide methods and apparatus for generating complex node representations of PNNI peer groups.
PNNI (Private Network-to-Network Interface) is a hierarchical, dynamic link-state routing protocol defined by the ATM (Asynchronous Transfer Mode) Forum for use in ATM networks. The hierarchy extension and the use of a single routing protocol at all levels of the hierarchy allow the support for large-scale ATM networks. Among the major characteristics of the protocol are signaling for switched virtual circuits (SVCs), dynamic routing capabilities, and support for quality of service (QoS) parameters. A key feature of the protocol is the ability to cluster network nodes into manageable groups called xe2x80x9cpeer groupsxe2x80x9d. One node in each peer group serves as the xe2x80x9cpeer group leaderxe2x80x9d and represents that peer group as a single logical node (a xe2x80x9clogical group nodexe2x80x9d) in the next layer up of the hierarchy. This concept is illustrated schematically in FIG. 1 of the accompanying drawings. In the figure, a peer group A in PNNI layer k consists of four nodes A1, A2, A3 and A4. Three of these nodes, nodes A1, A2 and A3, are border nodes. Each border node has a link connecting peer group A to another peer group (not explicitly shown in layer k), here peer groups B, C and D respectively. The topology in layer k is abstracted in the next layer up of the hierarchy, ie. layer k+1, such that each layer k peer group is represented as a single logical node in layer k+1. Thus peer group A is represented by node A in layer k+1, peer group B is represented by node B in layer k+1, and so on. In the figure, nodes A, B, C and D themselves form a peer group in layer k+1.
ATM is a source routing technology. To enable source route computation and to support end-to-end QoS (for example the required bandwidth), the nodes must maintain information about the network topology. PNNI thus defines a system for the creation and distribution of topology data within a network. Topology data is exchanged automatically by network nodes on a regular basis or upon significant changes to network topology so that each node maintains an up-to-date view of the network. The topology data is defined by PNNI Topology State Elements PTSE""s) which are created and distributed by nodes so that each node can maintain a topology database which defines its view of the network. This allows nodes to select paths for routing calls through the network, and to perform alternative routing in the case of link failure. PTSE""s include data defining topology characteristics derived from link or node state parameters. PTSE""s are flooded among nodes in a peer group so that each peer group node has the same topology database and thus the same view of the network. In the next level up of the hierarchy, however, the peer group topology is abstracted as described above, so that only the abstracted topology is seen by nodes sharing a peer group at this level. It is this topology abstraction that reduces the resources required to define very large networks.
The topology data required for path selection and routing may include not only details of the layout of nodes and links but also QoS parameters as mentioned above. For example, a call to be routed over the network may require a certain bandwidth. In this case, knowledge of the bandwidth of links in the network is required to determine if a call can be connected successfully. To allow such parameters to be taken into account, xe2x80x9ccostsxe2x80x9d can be associated with links and paths in the network. The cost of a link is expressed as an arbitrary value determined as some function of the parameter, eg. bandwidth, about which knowledge is required. Whatever the particular function employed, according to convention it is usual for the cost to be defined such that the lower the cost the better the link. In the case of bandwidth, for example, the cost C of a link may be defined as C=1/bandwidth. A path in the network, involving multiple links, can be measured by a xe2x80x9crestrictive costxe2x80x9d. According to the definition of restrictive cost, the weakest link in a path defines the restrictive cost of the path. Thus, when convention is followed such that a higher cost corresponds to a weaker link, the restrictive cost of a path will be determined by the maximum of the costs of the constituent links.
To allow such costs to be taken into account in the path selection process in spite of the hierarchical topology abstraction described above, PNNI provides a way to represent a peer group as a logical group node which has a more sophisticated structure than a single node. The two ways of representing a PNNI peer group in a higher layer are illustrated in FIG. 2 of the accompanying drawings. The left-hand side of the figure shows an example of the xe2x80x9csimple nodexe2x80x9d representation, and the right-hand side shows an example of the xe2x80x9ccomplex nodexe2x80x9d representation. The simple node representation shows the peer group as a single node A having ports P1, P2 and P3 connecting the node to external links, ie. links to neighboring peer groups. The simple node representation is simple to construct and use but does not give information about the cost of traversing the peer group. As discussed further below, a peer group can be modeled by an orientated graph in which a node of the peer group is referenced as a vertex of the graph, and a link between nodes is referenced as an edge between two vertices of the graph. The principle of the complex node representation is to map the simple node to a representation where:
the nucleus 1 is a vertex representing the node itself;
the nucleus 1 is connected via spokes 2 to a set of vertices P1, P2 and P3 each representing a port in the simple node representation; and
optionally, vertices representing ports can be directly connected by xe2x80x9cexception bypassesxe2x80x9d 3.
The complex node representation is derived using a set of restrictive costs for the peer group which is usually presented in the form of a cost matrix known as the xe2x80x9ctransition matrixxe2x80x9d for the peer group. The transition matrix defines the restrictive costs of paths between all pairs of border nodes in the peer group. Where there is more than one path between a given pair of border nodes, then ideally the optimal (lowest-cost) path determines the entry in the transition matrix. The complex node representation, derived on the basis of the transition matrix, indicates the cost of traversing the peer group, and therefore allows such costs to be taken onto account for path selection and other purposes.
The drawback of using the complex node representation is the increased processing complexity involved in generating the complex node representation and using this representation when computing routes (since there are more vertices and edges in the graph representing the network as a whole than in the case of the simple node representation). It is therefore desirable to provide an efficient method for generating the complex node representation and for the resulting complex node representation itself to be optimized as far as possible. In particular, there may be many possible complex node representations corresponding to a given transition matrix and hence a given peer group. In general it will be desirable to minimize the number of exception bypasses in the representation since these represent normal edges in the network graph and thus complicate the network topology seen by nodes. However, it is also important to ensure that the optimal paths of the resulting representation have the same cost as the optimal paths of the original peer group, ie. that the resulting representation accurately reflects the transition matrix.
Copending U.S. patent application Ser. No. 09/385,951, filed 30 Aug. 1999 and assigned to the Assignee of the present application, discloses one method for generating optimal complex node representations. This method is also discussed in xe2x80x9cOptimal PNNI Complex Node Representations for Restrictive Costs and Reduced Path Computation Timexe2x80x9d, I. Iliadis, 7th IFIP Workshop on Performance Modelling and Evaluation of ATM Networks, 28 Jun. 1999. The representations are optimal in the sense that they use the minimum number of exception bypasses within the class of complex node representations for which the path computation time is minimal. More specifically, the path computation time was explicitly restricted by considering the class of complex node representations which have the property that a restricted set of paths in the representation, specified a priori, always contains an optimal path. The higher the restriction imposed, the smaller the resulting set specified and thus the shorter the path computation time required (since fewer paths have to be considered). The particular restriction imposed in this case will be explained in more detail below. The method employed is based on the evolution process of a so-called xe2x80x9clogical group representationxe2x80x9d of the transition matrix. According to this process, the values of the restrictive costs in the transition matrix are considered in order. For each cost value C, logical groups of the border nodes are defined such that, for any arrangement of the border nodes in a given logical group, the overall restrictive cost of a set of paths which connects all the nodes in the group along a line is equal to C. When the last cost value is considered, the logical group representation is obtained in which groups for preceding cost values are nested. This will be discussed in more detail below.
Embodiments of the present invention provide methods for generating complex node representations which are similarly based on the evolution process of the logical group representation, but in which the class of complex node representations is not constrained as in U.S. Ser. No. 09/385,951. Moreover, use is made of the so-called xe2x80x9cspanning treexe2x80x9d representation of a network. The principles of spanning tree representations are described in xe2x80x9cSpanning Tree Method for Link State Aggregation in Large Communications Networksxe2x80x9d, W. Lee, Proc. IEEE INFOCOM ""95, Boston, vol. 1, pp. 297-302, April ""95, though this document is not concerned with the problem of generating complex node representations.
According to a first aspect of the present invention there is provided a method of generating a complex node representation of a peer group of nodes in a PNNI network system, wherein the peer group includes a plurality of border nodes, and a set of restrictive costs, defining the restrictive costs of respective paths between pairs of the border nodes, is stored in said system, the complex node representation being a representation of the peer group in which at least some of the border nodes are connected to a nucleus by respective spokes and a connection between a pair of the border nodes is represented by an exception bypass, the method comprising:
(a) for each cost value C of the restrictive costs in said set, defining one or more groups of said border nodes such that, for any arrangement of the border nodes in a said group, the restrictive cost of a set of said paths which connects all the nodes in the group along a line is equal to C;
(b) selecting said groups in order of cost value C;
(c) for each group selected in step (b), generating a complex node representation of the group by:
(c1) selecting a subset of the nodes within the group, said subset comprising either a said group for a preceding cost value C in said order which is not contained within another said group for a preceding cost value in said order, or a single node, in dependence on the contents of the currently-selected group;
(c2) for each of any said groups for a preceding cost value, which are not contained within another said group for a preceding cost value, among the remaining nodes outside the subset in the currently-selected group, defining a spoke of cost C for at least one node and defining a spoke of cost Vxe2x89xa7C for each other node, and for each of any single nodes, not forming part of a said group for a preceding cost value, among the remaining nodes outside the subset in the currently-selected group, defining a spoke of cost C,
(c3) for each of any said groups for a preceding cost value, which are not contained within another said group for a preceding cost value, among the remaining nodes outside the subset in the currently-selected group, defining one or more exception bypasses connecting the nodes in the group to form a spanning tree, each exception bypass having a cost equal to the restrictive cost of the path between the pair of border nodes connected thereby; and
(c4) incorporating the complex node representation of said subset of nodes, wherein, if said subset comprises a single node, the complex node representation of said subset comprises a spoke of cost Wxe2x89xa6C; and
(d) storing the complex node representation for the last group selected in step (b) as the complex node representation for the peer group.
Embodiments of the invention provide highly efficient methods for generating complex node representations of PNNI peer groups. There is no constraint on the location of optimal paths within the resulting representations, and this, coupled with the spanning tree arrangement of exception bypasses in step (c3), enables generation of complex node representations with the minimum possible number of exception bypasses.
The network system may be a single network or part thereof, or an internetwork, and the set of restrictive costs may be presented in the usual way in the form of a transition matrix. In some embodiments of the invention, the method may include generating the set of restrictive costs for the peer group prior to performing step (a).
As will be apparent from the detailed description below, the number of groups defined for each cost value in step (a) will depend on the particular set, or matrix, of costs for the peer group in question. Steps (c2) to (c4) may be performed in any order, and the cost V of spokes defined in step (c2) may be different for different spokes. If, at step (c3), there are no groups for a preceding cost value outside the subset in the currently-selected group, then clearly no exception bypasses will be defined here. Also, if such a group for a preceding cost value contains only one pair of nodes, then clearly only a single exception bypass will be defined for that group. Further, while in general a spanning tree connection can be used in step (c3), particular embodiments may use a spanning line connection here, a spanning line being a special degenerate case of a spanning tree as discussed further below.
Where, in step (a), said groups are defined in order of cost value C, then steps (b) and (c) may be performed in parallel with step (a). For example, steps (b) and (c) for the groups defined for a particular cost value might be performed immediately after those groups have been defined in step (a). Where the cost of a link is defined in accordance with the convention that the lower the cost, the better the link, then a lower restrictive cost will represent a better path. In this case, groups will be selected in step (b) in order of increasing cost value C. However, embodiments can be envisaged where costs are defined differently ie. the higher the cost the better the link. For example, the xe2x80x9ccostxe2x80x9d could be directly proportional to the parameter, such as bandwidth, by which a link is measured, or the cost might be that parameter itself. If the costs were defined in such a way, the restrictive cost of a path would be the minimum of the costs of the constituent links and a higher restrictive cost would represent a better path. In such cases, groups would be selected in step (b) in order of decreasing cost value C.
After generation of the complex node representation for the peer group, topology data in which this representation is defined can be distributed in the network system in the usual way as described above. Path selection in network nodes can then be performed using this topology data in known manner. Thus, according to a second aspect of the invention there is provided a method of distributing topology data in a PNNI network system, the system including a peer group of nodes, including a plurality of border nodes, for which a set of restrictive costs, defining the restrictive costs of respective paths between pairs of the border nodes, is stored in the system, the method comprising:
generating a complex node representation of the peer group by a method according to the first aspect of the invention; and
transmitting topology data, indicative of the complex node representation generated for the peer group, to at least one node of the network system outside the peer group.
In addition, according to a third aspect of the invention there is provided a method of selecting a path for routing a call in a PNNI network system, the system including a peer group of nodes, including a plurality of border nodes, for which a set of restrictive costs, defining the restrictive costs of respective paths between pairs of the border nodes, is stored in the system, the method comprising:
generating a complex node representation of the peer group by a method according to the first aspect of the invention;
transmitting topology data, indicative of the complex node representation generated for the peer group, to at least one node of the network system outside the peer group; and
at said node of the network system outside the peer group, selecting a path for routing of a call between a sending node of the system and a receiving node of the system, which receiving node is reachable from the sending node via said peer group, in dependence on the complex node representation.
In general, where features are described herein with reference to a method of the invention, corresponding features may be provided in accordance with apparatus of the invention, and vice versa. Thus, according to a fourth aspect of the invention there is provided apparatus for generating a complex node representation of a peer group of nodes, including a plurality of border nodes, in a PNNI network system, the complex node representation being a representation of the peer group in which at least some of the border nodes are connected to a nucleus by respective spokes and a connection between a pair of the border nodes is represented by an exception bypass, the apparatus comprising memory for storing a set of restrictive costs, defining the restrictive costs of respective paths between pairs of the border nodes, and control logic configured to:
(a) for each cost value C of the restrictive costs in said set, define one or more groups of said border nodes such that, for any arrangement of the border nodes in a said group, the restrictive cost of a set of said paths which connects all the nodes in the group along a line is equal to C;
(b) select said groups in order of cost value C;
(c) for each group selected in step (b), generate a complex node representation of the group by:
(c1) selecting a subset of the nodes within the group, said subset comprising either a said group for a preceding cost value C in said order which is not contained within another said group for a preceding cost value in said order, or a single node, in dependence on the contents of the currently-selected group;
(c2) for each of any said groups for a preceding cost value, which are not contained within another said group for a preceding cost value, among the remaining nodes outside the subset in the currently-selected group, defining a spoke of cost C for at least one node and defining a spoke of cost Vxe2x89xa7C for each other node, and for each of any single nodes, not forming part of a said group for a preceding cost value, among the remaining nodes outside the subset in the currently-selected group, defining a spoke of cost C;
(c3) for each of any said groups for a preceding cost value, which are not contained within another said group for a preceding cost value, among the remaining nodes outside the subset in the currently-selected group, defining one or more exception bypasses connecting the nodes in the group to form a spanning tree, each exception bypass having a cost equal to the restrictive cost of the path between the pair of border nodes connected thereby, and
(c4) incorporating the complex node representation of said subset of nodes, wherein, if said subset comprises a single node, the complex node representation of said subset comprises a spoke of cost Wxe2x89xa6C; and
(d) to store in said memory the complex node representation for the last group selected in step (b) as the complex node representation for the peer group.
Further aspects of the invention provide: a device for connection in a PNNI network system as a node of a PNNI peer group, which device comprises apparatus according to the fourth aspect of the invention; and a PNNI network system including one or more such devices. Another aspect of the invention provides a computer program product, readable by a processor of a device for connection in a PNNI network system as a node in a peer group of nodes, including a plurality of border nodes, for which a set of restrictive costs, defining the restrictive costs of respective paths between pairs of the border nodes, is stored in the system, said product comprising computer program code means executable by the processor to generate a complex node representation of said peer group by performing a method according to the first aspect of the invention.